문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 튜링 머신 (문단 편집) == 구성 == 튜링 머신은 아래와 같은 장치로 이루어진다: * 테이프(Tape): 일정한 크기의 셀(Cell)로 나뉘어 있는 종이 테이프. 각 셀에는 기호가 기록되어 있으며 길이는 무한히 늘어날 수 있다. * 헤드(Head): 종이 테이프의 특정 한 셀을 읽을 수 있는 헤드. 이동이 가능하다. 또는 헤드는 고정되어 있고 테이프가 이동한다. * 상태 기록기(State register): 현재 튜링 머신의 상태를 기록하고 있는 장치. * 개시 상태(Start state): 상태 기록기가 초기화된 상태를 의미한다. * 종료 상태(Halt state): 수행이 종료된 상태. * 행동표(Action table, transition table of instructions): 특정 상태에서 특정 기호를 읽었을 때 해야 할 행동을 지시한다. * 기호를 지우거나 고쳐 쓴다. * 헤드를 오른쪽, 왼쪽으로 한 칸 움직이거나 그 자리에 머문다. * 상태를 변경한다. 같은 상태에 머무를 수도 있다. 튜링 머신에서 종이 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 개수는 모두 유한해야 하며 서로 구분되어야 한다. 아래와 같은 개념을 일반화해 둔 것이다. * '현재 상태가 1인데 기호 'A'를 읽었다면 'B'를 기록하고 정지.' * '현재 상태가 1인데 기호 'B'를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경' * '현재 상태가 2인데 기호 'C'를 읽었다면 오른쪽으로 한 칸 이동'저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기